import java.util.*;
/**
 * @author LKQ
 * @date 2022/3/11 9:31
 * @description
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] parents = {-1, 2, 0, 2, 0};
        solution2.countHighestScoreNodes(parents);
    }
    private int[] L, R;
    private long maxPoint;
    private int maxCount, n;

    public int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        // 记录i下标的左节点，先覆盖为-1，有就覆盖上去
        L = new int[n];
        // 记录i下标的右节点
        R = new int[n];
        for (int i = 0; i < n; i++) {
            L[i] = R[i] = -1;
        }
        for (int node = 1; node < n; node++) {
            if (L[parents[node]] == -1) {
                L[parents[node]] = node;
            } else {
                R[parents[node]] = node;
            }
        }
        dp(0);
        return maxCount;
    }

    private int dp(int node) {
        if (node == -1) {
            return 0;
        }
        // node节点的左子树节点数目和右子树节点数目
        int l = dp(L[node]), r = dp(R[node]);
        // 删除任何一个节点都可以分为三部分：左子树节点数，右子树节点数（没有就置为1），除去这些后剩余节点数。
        long point = (long) Math.max(l, 1) * Math.max(r, 1) * Math.max(n - l - r - 1, 1);
        if (maxPoint < point) {
            maxPoint = point;
            maxCount = 1;
        } else if (maxPoint == point) {
            maxCount++;
        }
        return l + r + 1;
    }
}
